// Buffer cache.
//
// The buffer cache is a linked list of buf structures holding
// cached copies of disk block contents.  Caching disk blocks
// in memory reduces the number of disk reads and also provides
// a synchronization point for disk blocks used by multiple processes.
//
// Interface:
// * To get a buffer for a particular disk block, call bread.
// * After changing buffer data, call bwrite to write it to disk.
// * When done with the buffer, call brelse.
// * Do not use the buffer after calling brelse.
// * Only one process at a time can use a buffer,
//     so do not keep them longer than necessary.


#include "types.h"
#include "param.h"
#include "spinlock.h"
#include "sleeplock.h"
#include "riscv.h"
#include "defs.h"
#include "fs.h"
#include "buf.h"

// 修改1: 定义哈希桶相关常量
// 原因: 实现哈希桶方式管理缓冲区，减少锁竞争
#define NBUCKET 13
#define NBUFFER CEIL(NBUF, NBUCKET)
#define CEIL(num, divisor) (((num) + (divisor) - 1) / (divisor))

// 修改2: 将bcache结构体改为数组，长度为质数13
// 原因: 使用多个哈希桶来减少锁竞争，提高并发性能
struct {
  struct spinlock lock;
  struct buf buf[NBUFFER];
} bcache[NBUCKET];

// 修改3: 添加全局时间戳变量
// 原因: 用于实现LRU替换算法，记录缓冲区使用时间
static uint global_timestamp;

// 修改4: 添加哈希函数声明
// 原因: 用于计算缓冲区在哈希桶中的位置
uint hash(uint blockno);
// 修改5: 添加时间戳更新函数声明
// 原因: 用于更新缓冲区的时间戳
void update_timestamp(struct buf *b);

void
binit(void)
{
  struct buf *b;

  // 修改6: 初始化每个哈希桶的锁和缓冲区
  // 原因: 每个哈希桶独立管理，需要独立的锁
  for (int i = 0; i < NBUCKET; i++) {
      initlock(&bcache[i].lock, "bcache");
      for (int j = 0; j < NBUFFER; j++) {
          bcache[i].buf[j].timestamp = 0;
          initsleeplock(&bcache[i].buf[j].lock, "buffer");
      }
  }
}

// 修改7: 实现哈希函数
// 原因: 计算缓冲区在哈希桶中的位置
uint
hash(uint blockno)
{
    return blockno % NBUCKET;
}

// 修改8: 实现时间戳更新函数
// 原因: 更新缓冲区的时间戳，用于LRU替换算法
void
update_timestamp(struct buf *b)
{
    b->timestamp = __sync_fetch_and_add(&global_timestamp, 1);
//    printf("time %d\n",b->timestamp);
}

// Look through buffer cache for block on device dev.
// If not found, allocate a buffer.
// In either case, return locked buffer.
static struct buf*
bget(uint dev, uint blockno)
{
  struct buf *b;
  // 修改9: 根据块号计算哈希桶索引
  // 原因: 确定在哪个哈希桶中查找或分配缓冲区
  uint bucket_id = hash(blockno);

  // 修改10: 只在对应的哈希桶中查找
  // 原因: 减少锁的粒度，提高并发性能
  acquire(&bcache[bucket_id].lock);
  for(int i = 0; i < NBUFFER; i++) {
    b = &bcache[bucket_id].buf[i];
    if(b->dev == dev && b->blockno == blockno) {
      b->refcnt++;
      update_timestamp(b);
      release(&bcache[bucket_id].lock);
      acquiresleep(&b->lock);
      return b;
    }
  }
  release(&bcache[bucket_id].lock);

  // 修改11: 寻找空闲缓冲区，实现LRU替换算法
  // 原因: 在所有哈希桶中寻找最久未使用的缓冲区进行替换
  uint min_timestamp = 0xffffffff;
  struct buf *least_used_buf = 0;

  for(int i = 0, cur_bucket = bucket_id; i < NBUCKET; i++, cur_bucket++) {
    if(cur_bucket == NBUCKET)
      cur_bucket = 0;

    acquire(&bcache[cur_bucket].lock);
    for(int j = 0; j < NBUFFER; j++) {
      b = &bcache[cur_bucket].buf[j];
      if(b->refcnt == 0) {
        b->dev = dev;
        b->blockno = blockno;
        b->valid = 0;
        b->refcnt = 1;
        update_timestamp(b);

        release(&bcache[cur_bucket].lock);
        acquiresleep(&b->lock);
        return b;
      }

      if(b->timestamp < min_timestamp) {
        min_timestamp = b->timestamp;
        least_used_buf = b;
      }
    }
    release(&bcache[cur_bucket].lock);
  }

  // 修改12: 使用LRU算法选择的缓冲区
  // 原因: 替换最久未使用的缓冲区
  if(least_used_buf) {
    acquire(&bcache[bucket_id].lock);
    least_used_buf->dev = dev;
    least_used_buf->blockno = blockno;
    least_used_buf->valid = 0;
    least_used_buf->refcnt = 1;
    update_timestamp(least_used_buf);
    release(&bcache[bucket_id].lock);
    acquiresleep(&least_used_buf->lock);
    return least_used_buf;
  }

  panic("bget: no buffers");
}

// Return a locked buf with the contents of the indicated block.
struct buf*
bread(uint dev, uint blockno)
{
  struct buf *b;

  b = bget(dev, blockno);
  if(!b->valid) {
    virtio_disk_rw(b->dev, b, 0);
    b->valid = 1;
  }
  return b;
}

// Write b's contents to disk.  Must be locked.
void
bwrite(struct buf *b)
{
  if(!holdingsleep(&b->lock))
    panic("bwrite");
  virtio_disk_rw(b->dev, b, 1);
}

// Release a locked buffer.
// Move to the head of the MRU list.
void
brelse(struct buf *b)
{
  if(!holdingsleep(&b->lock))
    panic("brelse");

  releasesleep(&b->lock);

  // 修改13: 根据b->blockno计算哈希桶索引
  // 原因: 确定在哪个哈希桶中更新引用计数
  int bucket_id = hash(b->blockno);
  acquire(&bcache[bucket_id].lock);
  b->refcnt--;
  release(&bcache[bucket_id].lock);
}

void
bpin(struct buf *b) {
  // 修改14: 根据b->blockno计算哈希桶索引
  // 原因: 确定在哪个哈希桶中更新引用计数
  int bucket_id = hash(b->blockno);
  acquire(&bcache[bucket_id].lock);
  b->refcnt++;
  release(&bcache[bucket_id].lock);
}

void
bunpin(struct buf *b) {
  // 修改15: 根据b->blockno计算哈希桶索引
  // 原因: 确定在哪个哈希桶中更新引用计数
  int bucket_id = hash(b->blockno);
  acquire(&bcache[bucket_id].lock);
  b->refcnt--;
  release(&bcache[bucket_id].lock);
}